class Solution {
public:
		int maxSubArray(vector<int> &nums) {
	int begin = 0, end = nums.size() - 1;
		return maxArray(nums, begin, end);
	}
	int maxArray(vector<int> &nums, int begin, int end){
		if (begin == end)
			return nums[begin];
		int mid = (begin + end) >> 1;
		int m1 = maxArray(nums, begin, mid);
		int m2 = maxArray(nums, mid + 1, end);
		// 从中向左地寻找最大和
		int i, left = nums[mid], now = nums[mid];
		for (i = mid-1; i >= begin; i--){
			now+= nums[i];
			left = max(now, left);
		}
		int right = nums[mid + 1];
		now = nums[mid + 1];
		for (i = mid+2; i <= end; i++){
			now += nums[i];
			right = max(right, now);
		}
		int m3 = left + right;
		return max(m1, max(m2, m3));
	}
	int maxSubArray(vector<int> &nums) {
			int result = nums[0], sum = nums[0];
		int len = nums.size();
		for (int i = 1; i < len; i++){
			if (sum > 0)
				sum += nums[i];
			else
				sum = nums[i];
			if (result < sum)
				result = sum;
		}
		return result;
	}
};